//n 座城市，从 0 到 n-1 编号，其间共有 n-1 条路线。因此，要想在两座不同城市之间旅行只有唯一一条路线可供选择（路线网形成一颗树）。去年，交通运输
//部决定重新规划路线，以改变交通拥堵的状况。 
//
// 路线用 connections 表示，其中 connections[i] = [a, b] 表示从城市 a 到 b 的一条有向路线。 
//
// 今年，城市 0 将会举办一场大型比赛，很多游客都想前往城市 0 。 
//
// 请你帮助重新规划路线方向，使每个城市都可以访问城市 0 。返回需要变更方向的最小路线数。 
//
// 题目数据 保证 每个城市在重新规划路线方向后都能到达城市 0 。 
//
// 
//
// 示例 1： 
//
// 
//
// 输入：n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
//输出：3
//解释：更改以红色显示的路线的方向，使每个城市都可以到达城市 0 。 
//
// 示例 2： 
//
// 
//
// 输入：n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
//输出：2
//解释：更改以红色显示的路线的方向，使每个城市都可以到达城市 0 。 
//
// 示例 3： 
//
// 输入：n = 3, connections = [[1,0],[2,0]]
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 2 <= n <= 5 * 10^4 
// connections.length == n-1 
// connections[i].length == 2 
// 0 <= connections[i][0], connections[i][1] <= n-1 
// connections[i][0] != connections[i][1] 
// 
//
// Related Topics 深度优先搜索 广度优先搜索 图 👍 139 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author ldltd
 * @date 2023-10-03 16:42:17
 * @description 1466.重新规划路线
 */
public class ReorderRoutesToMakeAllPathsLeadToTheCityZero{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new ReorderRoutesToMakeAllPathsLeadToTheCityZero().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 //这里的vis标记的是路线而非城市
	boolean [] vis;
    public int minReorder1(int n, int[][] connections) {
		vis=new boolean[n];
		//使用数组，局部变量，传参的时候就可以改变
		int [] res=new int[]{0};
		List<List<Integer>> g=new ArrayList<>();
		for (int i = 0; i < n; i++) {
			g.add(new ArrayList<>());
		}
		//还是保存标号好一点
		for (int i = 0; i < connections.length; i++) {
			g.get(connections[i][0]).add(i);
			g.get(connections[i][1]).add(i);
		}
		dfs(g,0,connections,res);
		return res[0];
    }
	private void dfs(List<List<Integer>> g,int i,int[][] connections,int [] res){
		for (Integer integer : g.get(i)) {
			if(vis[integer]) continue;
			vis[integer]=true;
			//判断方向是否一致
			int out = connections[integer][0];
			int in= connections[integer][1];
			if(i==out) {
				res[0]++;
				dfs(g,in,connections,res);
			}else {
				dfs(g,out,connections,res);
			}

		}
	}

	public int minReorder(int n, int[][] connections) {
		vis=new boolean[n];
		List<List<Integer>> g=new ArrayList<>();
		//这里类似领接表，把所有和节点相关的点都加入
		//后面遍历是，只要查找connections里面对应的下标就行了
		for (int i = 0; i < n; i++) {
			g.add(new ArrayList<>());
		}
		for (int i = 0; i < connections.length; i++) {
			g.get(connections[i][0]).add(i);
			g.get(connections[i][1]).add(i);
		}
		int res=0;
		Deque<Integer> q=new LinkedList<>();
		//q存的是城市编号
		q.offer(0);
		while (!q.isEmpty()){
			Integer poll = q.poll();
			//对节点poll相邻的节点进行遍历，通过存储的在g的下标进行遍历
			for (Integer integer : g.get(poll)) {
				if(vis[integer]) continue;
				//标记当前城市访问过
				vis[integer]=true;
				//起点和终点
				int i = connections[integer][0];
				int j= connections[integer][1];
				//如果是当前点poll是起点，要变终点
				res+=i==poll?1:0;
				//检查poll的临近点
				//比如 0的临近是 0-》1   2——》0，  对1来说队列加入j, 对2来说队列加入i
				i=(i==poll)?j:i;
				q.offer(i);
			}
		}
		return res;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
